1. Field of Invention
The present invention relates generally to mass digital data storage systems. More particularly, the present invention relates to systems and methods for enabling an error correction scheme to be dynamically changed by allowing error correction codes stored in a redundant area associated with a physical block to be dynamically altered.
2. Description of the Related Art
The use of non-volatile memory systems such as flash memory storage systems is increasing due to the compact physical size of such memory systems, and the ability for non-volatile memory to be repetitively reprogrammed. The compact physical size of flash memory storage systems facilitates the use of such storage systems in devices which are becoming increasingly prevalent. Devices which use flash memory storage systems include, but are not limited to, digital cameras, digital camcorders, digital music players, handheld personal computers, and global positioning devices. The ability to repetitively reprogram non-volatile memory included in flash memory storage systems enables flash memory storage systems to be used and reused.
Often, in order to assure the accuracy of data stored in physical blocks of a flash memory, an error correction code (ECC) algorithm, or an error checking and correction code algorithm, may be used to encode data for storage, and to decode the stored data. Typically, ECC algorithms use dedicated circuitry or software to encode and to decode the data. Many ECC algorithms or methods may add a parity bit or parity bits which may be used to both detect and to correct errors associated with stored data. Such parity bits may be added in redundant areas associated with physical blocks.
FIG. 1 is a diagrammatic representation of a redundant area of a page of a physical block. A physical block 200 includes pages 204. A page 204a, which is generally representative of pages 204a-h, has a data area 208 that contains user data and a redundant area 212. Data area 208 often includes approximately 512 or more bytes, while redundant area 212 often includes approximately sixteen or more bytes. Redundant area 212 generally includes information such as a logical block address 220 for a logical block (not shown) that is associated with physical block 200 and ECC bits 224. ECC bits 224, which may occupy approximately eight bytes in redundant area 212, are used to encode and to decode data contained in data area 208 and portions of redundant area 212. It should be appreciated that redundant area 212 also includes other information 216.
Some ECC algorithms that are used to encode and to decode data for storage are known as 1-bit ECC algorithms, 2-bit ECC algorithms, and 2-symbol ECC algorithms. 1-bit ECC algorithms enable a set of symbols to be represented such that if one bit of the representation is incorrect, e.g., is flipped, the bits will be corrected, and if two bits are incorrect, e.g., are flipped, the bits may still be correctly identified. 2-bit ECC algorithms enable a set of symbols to be represented such that if two bits of the representation are flipped or otherwise incorrect, the two bits will be corrected, and if more than two bits are flipped, the bits may still be correctly identified. 2-symbol ECC algorithms may be used to such that when two symbols which are each made up of five bits include incorrect bits, as for example bits that are flipped, those two symbols may be correctly identified. The use of 2-symbol ECC algorithms allows for up to ten incorrect bits to be corrected, when the ten incorrect bits are located in two symbols.
In general, the use of a 2-bit ECC algorithm may be preferred to a 1-bit ECC algorithm due to the ability to of a 2-bit ECC algorithm to detect more than two bad bits and to correct two bits, while a 1-bit ECC algorithm may detect two bad bits and to correct one bit. The use of a 2-symbol ECC algorithm may be preferred to a 2-bit ECC algorithm because of the ability to correct up to ten incorrect bits in some cases. However, the implementation of a 2-symbol ECC algorithm, while providing increased error correction capabilities to stored data, generally involves more calculations and, hence, more computational overhead than the implementation of a 2-bit ECC algorithm. Similarly, the implementation of a 2-bit ECC algorithm may also use more computational overhead than the implementation of a 1-bit ECC algorithm. When more computational overhead is required, more power, e.g., battery power, may be consumed by a non-volatile memory. As a result, the overall performance of a memory system may be compromised, particularly since the integrity of data that is stored in blocks which have been erased a relatively low number of times is generally relatively high.
To reduce the computational and power requirements associated with implementing 2-bit ECC and 2-symbol ECC algorithms, some systems may use 1-bit ECC algorithms to encode and to decode data. 1-bit ECC algorithms, however, are often less accurate than 2-bit ECC and 2-symbol ECC algorithms. Further, as blocks into which data is stored near the end of their usable lives, the data stored in such blocks is more likely to contain errors. As such, when 1-bit ECC algorithms are used to encode data stored in blocks which have been erased a relatively high number of times and to decode such data, the integrity of the data may be compromised, and the performance associated with the blocks may be adversely affected.
Therefore, what is needed is a method and an apparatus which enables the performance of blocks which have been erased a relatively high number of times to be improved without requiring relatively high computational overhead and performance penalties to encode and to decode data which are stored in blocks that have been erased a relatively low number of times. That is, what is desired is a method and an apparatus that enables contents of blocks to be encoded using different ECC algorithms which may be dynamically configured such that the ECC algorithm may be changed depending upon how many times the blocks have been erased.